package rangeSumBST

// Definition for a binary tree node.
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func rangeSumBST(root *TreeNode, low int, high int) int {

	if root == nil {
		return 0
	}

	if root.Val == low {
		return root.Val + rangeSumBST(root.Right, low, high)
	}
	if root.Val == high {
		return root.Val + rangeSumBST(root.Left, low, high)
	}
	if root.Val < high && root.Val > low {
		return root.Val + rangeSumBST(root.Left, low, high) + rangeSumBST(root.Right, low, high)
	}
	if root.Val < low {
		return rangeSumBST(root.Right, low, high)
	}
	if root.Val > high {
		return rangeSumBST(root.Left, low, high)
	}
	return 0
}
